package nfa_generator;

import java.util.ArrayList;
import java.util.List;
import ast_generator.ASTNode;
import ast_generator.ASTTree;

public class NFAGenerator {
	private List<ASTTree> astTreeList;
	private List<NFAGraph> nfaList;
	private NFAGraph finalGraph;
	
	/**
	 * Constructor for NFAGenerator, takes in a list of ASTTrees.
	 * @param ASTTree
	 */
	public NFAGenerator(List<ASTTree> astTreeList) {
		
		this.astTreeList = astTreeList;
		nfaList = new ArrayList<NFAGraph>();
		finalGraph = null;
	}
	
	/**
	 * Constructs an NFA graph for the language from the given AST trees.
	 * @param ASTTree
	 */
	public NFAGraph generateNFA() {
		
		for(ASTTree tree : astTreeList) {
			nfaList.add(traversal(tree.getRoot(), tree.getTokenType(), null));
		}
		
		finalGraph = new NFAGraph(new NFANode());
		for(NFAGraph graph : nfaList) {
			finalGraph.getStartState().addTransition("epsilon", graph.getStartState());
			finalGraph.addStates(graph.getStates());
			finalGraph.addFinalEndState(graph.getEndState());
		}
		
		int n = 0;
		for(NFANode node : finalGraph.getStates()) {
			node.setName("" + n);
			n++;
		}
		return finalGraph;
	}
	
	public NFAGraph traversal(ASTNode astNode, String tokenType, NFAGraph graph) {
		NFAGraph left = null;
		NFAGraph right = null;
		NFAGraph root = null;

		if(astNode == null) {
			return null;
		}
		
		left = traversal(astNode.getLeft(), tokenType, graph);
		right = traversal(astNode.getRight(), tokenType, graph);
		
		if(left == null && right == null && astNode.isInput()) {
			root = getPrimitiveGraph(astNode.getValue(), tokenType);
		}
		else if(left != null && right != null && astNode.isOperation()) {
			if(astNode.getValue().compareTo(" ") == 0) {
				root = operatorConcatenation(left, right);
			}
			else if(astNode.getValue().compareTo("|") == 0) {
				root = operatorAlternation(left, right);
			}
		}
		else if(left != null && right == null && astNode.isOperation()) {
			if(astNode.getValue().compareTo("*") == 0) {
				root = operatorReplication(left);
			}
			else if(astNode.getValue().compareTo("+") == 0) {
				root = operatorReplicationPlus(left);
			}
			else if(astNode.getValue().compareTo("?") == 0) {
				root = operatorQuestionMark(left);
			}
		}
		
		return root;
	}
	
	/**
	 * Builds a primitive, two-node graph for a given input and returns it.
	 * @param input
	 * @return
	 */
	public NFAGraph getPrimitiveGraph(String input, String token) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(input, endState);
		endState.setToken(token);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, concatenates them using an epsilon transition, and returns the new graph.
	 * @param g1
	 * @param g2
	 * @return
	 */
	public NFAGraph operatorConcatenation(NFAGraph g1, NFAGraph g2) {
		g1.getEndState().addTransition("epsilon", g2.getStartState());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph();
		newGraph.setStartState(g1.getStartState());
		newGraph.setEndState(g2.getEndState());
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g2.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, ORs them using espison transitions, and returns the new graph.
	 * @param g1
	 * @param g2
	 * @return
	 */
	public NFAGraph operatorAlternation(NFAGraph g1, NFAGraph g2) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		startState.addTransition("epsilon", g2.getStartState());
		
		g1.getEndState().addTransition("epsilon", endState);
		g2.getEndState().addTransition("epsilon", endState);
		
		endState.setToken(g2.getEndState().getToken());
		g1.getEndState().setToken(null);
		g2.getEndState().setToken(null);
		

		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g2.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the replication, or Kleene Enclosure, operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorReplication(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		startState.addTransition("epsilon", endState);
		g1.getEndState().addTransition("epsilon", g1.getStartState());
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the one or more replication operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorReplicationPlus(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		g1.getEndState().addTransition("epsilon", g1.getStartState());
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Unused??
	 * 
	 * Takes in a graph, applies the zero or one operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorQuestionMark(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		startState.addTransition("epsilon", endState);
		endState.setToken(g1.getEndState().getToken());
		g1.getEndState().setToken(null);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}	
}